package 左神算法.排序;

/**
 * 希尔排序 基于插入排序的基础上进行改良的排序算法
 * <p>
 * 首先按照一定的间隔gap，然后在规定的gap中使用插入排序进行排序，
 * 第一轮处理后大致的 小数在前，大数在后
 * 然后将间隔满满降低，
 * gap大 移动次数少，gap小，移动距离短
 * 但是并不稳定
 *
 * <p>
 *     希尔排序在实际工程中使用概率不是特别多，在面对的数据比较无规律的时候，使用希尔排序的整体时间复杂度比较平稳
 *     空间复杂度O(1)
 *     时间复杂度大概为O(n ^ 1.3) 推导的原理不是太了解
 * </p>
 *
 * @Author linhao
 * @Date created in 10:26 下午 2022/1/27
 */
public class ShellSort {

    public static int[] arr = {9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2};

    public static void sort(int[] arr) {
        //gap每次排序之后都要缩小一倍，所以是gap/=2
        for (int gap = 4; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int k = i; k > gap - 1; k -= gap) {
                    if (arr[k] < arr[k - gap]) {
                        swap(arr, k, k - gap);
                    }
                }
            }
        }
    }

    /**
     * 如果是需要考虑到数组个数非常多的情况下，可以将gap设置为arr的一半
     *
     * @param arr
     */
    public static void sortV2(int[] arr) {
        //gap每次排序之后都要缩小一倍，所以是gap/=2
        for (int gap = arr.length >> 1; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int k = i; k > gap - 1; k -= gap) {
                    if (arr[k] < arr[k - gap]) {
                        swap(arr, k, k - gap);
                    }
                }
            }
        }
    }

    /**
     * 如果是需要考虑到数组个数非常多的情况下，可以将gap设置为arr的一半
     * knuth序列
     * h=1
     * h=3*h-1 当gap为整个数组长度的1/3左右为最佳
     *
     * @param arr
     */
    public static void sortV3(int[] arr) {
        int h = 1;
         while (h <= arr.length / 3) {
            h = 3 * h - 1;
        }
        for (int gap = h; gap > 0; gap = (gap - 1) / 3) {
            for (int i = gap; i < arr.length; i++) {
                for (int k = i; k > gap - 1; k -= gap) {
                    if (arr[k] < arr[k - gap]) {
                        swap(arr, k, k - gap);
                    }
                }
            }
        }
    }


    public static void swap(int[] arr, int j, int p) {
        int temp = arr[j];
        arr[j] = arr[p];
        arr[p] = temp;
    }

    public static void displayArr() {
        for (Integer integer : arr) {
            System.out.print(integer + " ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        ShellSort.sort(arr);
        ShellSort.displayArr();
    }
}
